package org.example.leetcode.interview.queue;

import org.example.util.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

class LC0230 {
    public int kthSmallest(TreeNode root, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (queue.size() < k) {
                queue.offer(node.val);
            } else if (queue.peek() > node.val) {
                queue.poll();
                queue.offer(node.val);
            }
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return queue.peek();
    }
}
